import java.util.Scanner;

public class Test4 {
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            char[] c1 = in.nextLine().toCharArray();
            char[] c2 = in.nextLine().toCharArray();
            int len1 = c1.length;
            int len2 = c2.length;
            int[][] dp = new int[len1+1][len2+1];
            for (int i = 1; i <= len1; i++) {
                for (int j = 1; j <= len2; j++) {
                    if (i < j) {
                        if (c1[i-1] == c2[j-1]) {
                            dp[i][j] = dp[i-1][j-1] + 1;
                        } else {
                            dp[i][j] = dp[i-1][j-1];
                        }
                    }
                }
            }
            System.out.println(len1-dp[len1][len2]);
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String str1 = in.nextLine();
            String str2 = in.nextLine();
            int len1 = str1.length();
            int len2 = str2.length();
            // 分三种情况：
            // 1.只在前面添加字符 2.只在后面添加字符 3.前面和后面都添加字符
            int ret = 0x3f3f3f3f;
            for (int i = 0; i < len2-len1+1; i++) {
                StringBuilder sb = new StringBuilder(str2);
                ret = Math.min(ret, getDiffLength(str1, sb.substring(i, i+len1)));
            }
            System.out.println(ret);
        }
    }

    private static int getDiffLength(String str1, String str2) {
        char[] c1 = str1.toCharArray();
        char[] c2 = str2.toCharArray();
        int count = 0;
        for (int i = 0; i < c1.length; i++) {
            if (c1[i] != c2[i]) {
                count++;
            }
        }
        return count;
    }
}
